Packet-transfer devices in high-speed data networks, such as switches and routers, are required to perform flexible and sophisticated packet classification at high speed. For this purpose, many network devices use ternary content-addressable memory (TCAM) components to store rules that are to be applied in processing packets. To search the TCAM, several fields of the packet (typically header fields) are concatenated to form a key. A match between the key and a given TCAM entry can be used to trigger various actions in the network device, such as forwarding decisions, packet encapsulation and de-capsulation, security filtering, and quality of service classification.
TCAM is advantageous in that it is able to hold rule entries that contain not only ones and zeroes, to be matched against the key, but also “don't care” bits, which will match either a zero or a one in the key. These “don't care” bits in the TCAM entries are commonly referred to as “masked” bits, while bits having a defined value (1 or 0) are referred to as “unmasked.” TCAM thus affords a high degree of flexibility in rule definition.
U.S. Patent Application Publication 2017/0052731, whose disclosure is incorporated herein by reference, describes a method for classification that includes extracting respective classification keys from a collection of data items and receiving a corpus of rules for matching to the classification keys. At least some of the rules include masked bits in addition to the unmasked bits. Rule patterns are extracted from the corpus, defining different, respective sequences of masked and unmasked bits to which one or more of the rules conform. The rule patterns are grouped into extended rule patterns, such that the respective set of unmasked bits in any rule pattern is a superset of the unmasked bits in the extended rule pattern into which it is grouped. Rule entries corresponding to the rules are computed using the extended rule patterns and are stored in a random access memory (RAM). The data items are classified by matching the respective classification keys to the rule entries in the RAM.